//
// Created by jerry on 2024/8/30.
//

#ifndef DATASTRUCTURE_TESTRBTREE_H
#define DATASTRUCTURE_TESTRBTREE_H
#include <iostream>
using std::size_t;
using std::pair;
using std::cin;
using std::cout;
using std::endl;
//考虑到假期里写的红黑树已经有些遗忘，这里我再建一个，不再使用
namespace testCode{
    enum color{
        black,
        red,
    };
    template <class T>
    struct RBTreeNode{
        explicit RBTreeNode(T&& val,RBTreeNode<T>* left = nullptr
                ,RBTreeNode<T>* right = nullptr,RBTreeNode<T>* parent = nullptr):
                _val(std::forward<T>(val)),_left(left),_right(right),_parent(parent)
        {}//这里还是使用了引用折叠
        explicit RBTreeNode(const T& val,RBTreeNode<T>* left = nullptr
                ,RBTreeNode<T>* right = nullptr,RBTreeNode<T>* parent = nullptr):
                _val((val)),_left(left),_right(right),_parent(parent)
        {}//这里还是使用了引
        T _val;
        enum color _col = red;
        RBTreeNode<T>* _left;
        RBTreeNode<T>* _right;
        RBTreeNode<T>* _parent;//这里还是使用三叉链的结构
    };
    template <class T,class Compare = std::less<T>>
    class RBTree{
    public:
        RBTree() = default;
        typedef RBTreeNode<T> Node;
        void RotateLeft(Node* root)
        {
            Node* tmp = root->_parent;
            Node* child = root->_right;
            root->_right = child->_left;
            if(child->_left) child->_left->_parent = root;
            //由于这里是三叉链，还要维护三叉链的结构
            root->_parent = child;
            child->_left = root;
            //child和源根的关系
            child->_parent = tmp;
            if(tmp)
            {
                if(root == tmp->_left) tmp->_left = child;
                else tmp->_right = child;
            }
        }
        void RotateRight(Node* root)
        {
            Node* tmp = root->_parent;
            Node* child = root->_left;
            root->_left = child->_right;
            if(child->_right) child->_right->_parent = root;
            //由于这里是三叉链，还要维护三叉链的结构
            root->_parent = child;
            child->_right = root;
            //child和源根的关系
            child->_parent = tmp;
            if(tmp)
            {
                if(root == tmp->_left) tmp->_left = child;
                else tmp->_right = child;
            }

        }

        void CheckTree(RBTreeNode<T>* cur) {
            if (cur == nullptr) return;
            Node *parent = cur->_parent;
            while (parent) {
                if (cur->_col == black) return;
                else if (parent->_col == black) return;
                Node *grandP = parent->_parent;
                if (grandP == nullptr) {
                    parent->_col = black;
                    return;
                }
                Node *uncle = nullptr;
                if (parent == grandP->_left) uncle = grandP->_right;
                else uncle = grandP->_left;
                if (uncle && uncle->_col == red) {
                    parent->_col = uncle->_col = black;
                    grandP->_col = red;
                    cur = grandP;
                    parent = cur->_parent;//这里就是继续进行check
                } else {
                    if (grandP->_right == parent && parent->_right == cur) {
                        RotateLeft(grandP);
                        parent->_col = black;
                        cur->_col = grandP->_col = red;
                        break;//这里就是可以退出了
                    } else if (grandP->_left == parent && parent->_left == cur) {
                        RotateRight(grandP);
                        parent->_col = black;
                        cur->_col = grandP->_col = red;
                        break;
                    } else if (grandP->_right == parent && cur == parent->_left) {
                        RotateRight(parent);
                        RotateLeft(grandP);
                        cur->_col = black;
                        parent->_col = grandP->_col = red;
                        break;
                    } else {
                        RotateLeft(parent);
                        RotateRight(grandP);
                        cur->_col = black;
                        parent->_col = grandP->_col = red;
                        break;
                    }


                }

            }
            if(_root){
                while(_root->_parent)
                    _root = _root->_parent;
            }
        }
        bool insert(T&& val)
        {
            if(_root == nullptr) {
                _root = new RBTreeNode<T>(std::forward<T>(val));//这里注意移动语义
                _root->_col = black;
                return true;
            }
            RBTreeNode<T>* cur = _root;
            RBTreeNode<T>* parent = nullptr;
            while(cur)//这里需要找到一个空节点的位置来insert
            {
                parent = cur;
                if(_cmp(val,cur->_val)) cur = cur->_left;
                else if(_cmp(cur->_val,val)) cur = cur->_right;
                else return false;//已经存在
            }
            int dir = 0;
            if(_cmp(val,parent->_val)) dir = 0;//左
            else dir = 1;//右
            RBTreeNode<T>* newnode = new RBTreeNode<T>(std::forward<T>(val));//新增节点
            _size++;
            newnode->_parent = parent;
            if(dir == 0) parent->_left = newnode;
            else parent->_right = newnode;
            cur = newnode;
            CheckTree(cur);//检查红黑树的合法性
            return true;
        }
        bool insert(const T& val)
        {
            if(_root == nullptr) {
                _root = new RBTreeNode<T>((val));//这里注意移动语义
                _root->_col = black;
                return true;
            }
            RBTreeNode<T>* cur = _root;
            RBTreeNode<T>* parent = nullptr;
            while(cur)//这里需要找到一个空节点的位置来insert
            {
                parent = cur;
                if(_cmp(val,cur->_val)) cur = cur->_left;
                else if(_cmp(cur->_val,val)) cur = cur->_right;
                else return false;//已经存在
            }
            int dir = 0;
            if(_cmp(val,parent->_val)) dir = 0;//左
            else dir = 1;//右
            RBTreeNode<T>* newnode = new RBTreeNode<T>((val));//新增节点
            _size++;
            newnode->_parent = parent;
            if(dir == 0) parent->_left = newnode;
            else parent->_right = newnode;
            cur = newnode;
            CheckTree(cur);//检查红黑树的合法性
            return true;
        }


        size_t size() const { return _size; }
        pair<bool,int> isValid(Node* root)
        {
            if(root == nullptr) return std::make_pair(true,0);
            pair<bool,int> lhs = isValid(root->_left);
            if(lhs.first == false) return std::make_pair(false,-1);
            pair<bool,int> rhs = isValid(root->_right);
            if(rhs.first == false) return std::make_pair(false,-1);
            if(lhs.second != rhs.second) return std::make_pair(false,-1);
            if(root->_col == black) return std::make_pair(true,rhs.second + 1);
            else {
                if((root->_left && root->_left->_col == red) || (root->_right && root->_right->_col == red)) return std::make_pair(false,-1);
                else return std::make_pair(true,rhs.second);
            }
        }
        bool CheckValid()
        {
            return isValid(_root).first;
        }

    private:
        RBTreeNode<T>* _root = nullptr;
        size_t _size = 0;
        Compare _cmp;
    };
}

#endif //DATASTRUCTURE_TESTRBTREE_H
